package algorithm.bitmanipulation;

/**
 * 268. Missing Number
 * LeetCode: https://leetcode.com/problems/missing-number/
 * Difficulty: Easy
 * Related Topics: Array, Math, Bit Manipulation
 *
 * 给一个数组，数组里包含n个不同的数字，例如 0,1,2,3......n
 * 找到其中缺失的一个数字。
 *
 * 举栗：
 * Input: {3,0,1}
 * Output: 2
 *
 * Input: {9,6,4,2,3,5,7,0,1}
 * Output: 8
 *
 * 【要求】：线性时间，常量空间
 *
 * Created by yzy on 2019-05-06 19:31
 */
public class MissingNumber {

    public static void main(String[] args) {
        int[] arr = new int[]{3,0,2};
        System.out.println(missingNumber(arr));
    }


    /**
     * 思路：
     * 利用异或运算符（^），两个相同的数字异或之后为0
     * 遍历数组异或之后，再逐个异或数组的下标，从0到数组长度
     * 注意：要比数组数元素多一个，这样在数组中的所有元素都异或了一遍为0，留下的那个数字就是结果。
     *
     * Runtime: 0ms (beats 100.0%)
     * Memory: 41.4MB (beats 60.55%)
     * @param nums
     * @return
     */
    public static int missingNumber(int[] nums) {
        int res = 0;
        for(int i=0; i<nums.length; i++){
            res = res ^ nums[i] ^ (i+1);
        }
        return res;
    }
}
